#include "myTree.h"
#include <bits/stdc++.h>
using namespace std;
MyTree::~MyTree(){};
TreeNode rem;
TreeNode *pre = NULL;
TreeNode *buildtree_first(string &s)
{
    TreeNode *tmp = new TreeNode;
    if (s[0] == '@')
        return NULL;
    tmp->data = s[0];
    tmp->leftChild = buildtree_first(s = s.substr(1, s.length() - 1));
    tmp->rightChild = buildtree_first(s = s.substr(1, s.length() - 1));
    return tmp;
}

void midinfsearch(TreeNode *s,char target)
{
    if (s == NULL)
    { // 若根节点为空则返回
        return;
    }
    TreeNode *p = s; // p为工作指针
    while (p != NULL)
    {
        while (p->lTag == Link)
        { // 结点有左树时，寻找最左端的树
            p = p->leftChild;
        }
        if(p->data==target)rem=*p;
        while (p != NULL && p->rTag == Thread)
        { // 节点非空并且右树是线索树时查找最前的一个线索树节点
            p = p->rightChild;
            // Visit(p);
            if(p->data==target)rem=*p;
        }
        p = p->rightChild; // 右树不是线索树，查找该节点的右孩子节点
    }
    return;
}

void presearch(TreeNode *p)
{
    if (p == NULL)
        return;
    cout << p->data;
    presearch(p->leftChild);
    presearch(p->rightChild);
    return;
}

void midsearch(TreeNode *p)
{
    if (p == NULL)
        return;
    midsearch(p->leftChild);
    cout << p->data;
    midsearch(p->rightChild);
    return;
}

void sufsearch(TreeNode *p)
{
    if (p == NULL)
        return;
    sufsearch(p->leftChild);
    sufsearch(p->rightChild);
    cout << p->data;
    return;
}

void pres(TreeNode *p, const char target)
{
    if (p == NULL)
        return;
    if (p->data == target)
        rem = *p;
    if (p->lTag == Link)
        pres(p->leftChild, target);
    if (p->rTag == Link)
        pres(p->rightChild, target);
    return;
}

void pres(TreeNode *p, int &sum)
{
    if (p == NULL)
        return;
    if (p->leftChild == NULL && p->rightChild == NULL)
        sum++;
    pres(p->leftChild, sum);
    pres(p->rightChild, sum);
    return;
}

void TreeNode::printNode()
{
    cout << this->data;
}

void Intreading(TreeNode *p)
{
    if (p == NULL)
        return;
    Intreading(p->leftChild);
    if (p->leftChild == NULL)
    {
        p->lTag = Thread;
        p->leftChild = pre;
    }
    if (pre != NULL && pre->rightChild == NULL)
    {
        pre->rTag = Thread;
        pre->rightChild = p;
    }
    pre = p;
    Intreading(p->rightChild);
    return;
}

TreeNode::TreeNode(char a, TreeNode *l, TreeNode *r, NodeTag ll, NodeTag rr)
{
    data = a;
    leftChild = l;
    rightChild = r;
    lTag = ll;
    rTag = rr;
}

TreeNode::TreeNode()
{
    new (this) TreeNode('\0', NULL, NULL, Link, Link);
}

TreeNode::~TreeNode(){};

MyTree::MyTree()
{
    root = NULL;
    isThread = false;
}

/*MyTree::MyTree(const char s[])
{
    int j = 0;
    for (j = 0; s[j] != 0; j++)
    {
        ch[j] = s[j];
    }
    ch[j] = 0;
    stack<TreeNode *> s; // 运用栈记录前序遍历的左节点，方便去根据结点指向右节点
    this->isThread = 0;
    int i = 0;
    if (ch[i] == '@')
        return;
    TreeNode *p;
    TreeNode *q;
    p = new TreeNode;
    this->root = p;
    p->data = ch[i];
    i++;
    num = 1; // 结点个数
    while ((ch[i] != '\0') || (!s.empty()))
    {
        if (p == NULL) // p的值为空则读取下一个数值
        {
            i++;
        }
        else // 不断建立左子树，直到遇到“@”即空值
        {
            while (ch[i] != '@')
            {
                q = new TreeNode;
                q->data = ch[i];
                p->leftChild = q;
                s.push(p); // 将遍历过的父结点记录在栈中
                p = q;
                i++;
                num++;
            }
            p->leftChild = NULL;
            s.push(p);
            i++;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop(); // 读取栈顶元素，去建立右子树，再以其为根节点去建立树
            if (ch[i] != '@')
            {
                q = new TreeNode;
                q->data = ch[i];
                p->rightChild = q;
                p = q;
                i++;
                num++;
            }
            else
            {
                p->rightChild = NULL;
                p = NULL;
            }
        }
    }
}*/
// 非递归建树
MyTree::MyTree(const char t[])
{
    string s = t;
    int j = 0;
    for (j = 0; t[j] != 0; j++)
    {
        chs[j] = t[j];
    }
    chs[j] = 0;
    root = buildtree_first(s);
}

MyTree::MyTree(const MyTree &T)
{
    new (this) MyTree(T.chs);
}

/*void MyTree::preOrderTraverse()
{
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (p != NULL || !s.empty())
    {
        while (p != NULL)
        {
            preorder += p->data;
            s.push(p);
            p = p->leftChild;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->rightChild;
        }
    }
    for(int i=0;i<preorder.size();i++)
    {
        cout<<preorder[i]<<endl;
    }
}*/
// 非递归前序遍历
void MyTree::preOrderTraverse()
{
    presearch(this->root);
    return;
}
/*
void MyTree::inOrderTraverse() // 中序遍历
{
  string ino = "\0"; // 保留中序遍历结果
  stack<TreeNode *> s;
  TreeNode *p = root;
  while (p != NULL || !s.empty())
  {
    while (p != NULL)
    {
      s.push(p);
      p = p->leftChild;
    }
    if (!s.empty())
    {
      p = s.top();
      ino += p->data;
      cout << p->data;
      s.pop();
      p = p->rightChild;
    }
  }
}
*/
// 非递归中序遍历
void MyTree::inOrderTraverse()
{
    midsearch(this->root);
    return;
}
/*
void MyTree::postOrderTraverse() // 后序遍历
{
  string post = "\0"; // 保留后序相反遍历结果
  stack<TreeNode *> s;
  TreeNode *p = root;
  while (p != NULL || !s.empty())
  {
    while (p != NULL)
    {
      post += p->data;
      s.push(p);
      p = p->rightChild;
    }
    if (!s.empty())
    {
      p = s.top();
      s.pop();
      p = p->leftChild;
    }
  }
  int len = post.size();
  for (int j = len - 1; j >= 0; j--)
  {
    cout << post[j];
  }
}
*/
// 非递归后序遍历
void MyTree::postOrderTraverse()
{
    sufsearch(this->root);
    return;
}

TreeNode &MyTree::locateNode(const char &v)
{
    if (!this->isThreadedTree())
    {
        pres(this->root, v);
        return rem;
    }
    midinfsearch(this->root,v);
    return rem;
}

int MyTree::countLeaf()
{
    int sum = 0;
    pres(this->root, sum);
    return sum;
}

int MyTree::height(const TreeNode *root)
{
    int m, n;
    if (root == NULL)
        return 0;
    else
    {
        m = height(root->leftChild);  // 左子树高度
        n = height(root->rightChild); // 右子树高度
    }
    return (m > n) ? m + 1 : n + 1; // 取高的加1
}

int MyTree::countHeight() // 计算树的深度
{
    return height(root);
}

bool MyTree::isThreadedTree() // 判断是否为线索二叉树
{
    return isThread;
}

bool MyTree::inOrderThreading()
{
    pre = NULL;
    this->isThread = true;
    Intreading(this->root);
    return true;
}

TreeNode *Lastnode(TreeNode *p)
{
    //循环找到最右下的结点（不一定是叶子结点）
    while(p->rTag == Link) p=p->rightChild;
    return p;
}

TreeNode *Firstnode(TreeNode *p)
{
    //循环找到最左下角结点（不一定是叶子结点）
    while(p->lTag==Link) p=p->leftChild;
    return p;
}

TreeNode &MyTree::preNode(const TreeNode &T)
{
    if(T.lTag==Thread)return *T.leftChild;
    return *Lastnode(T.leftChild);
}

TreeNode &MyTree::nextNode(const TreeNode &T)
{
   if(T.rTag==Thread)return *T.rightChild;
   return *Firstnode(T.rightChild);
}
HuffmanTree::HuffmanTree(const int &x, const int ch[]) // 构造函数
{
    n = x;
    m = 2 * n - 1;
    for (int i = 0; i < n; i++)
        t[i].w = ch[i];
    for (int i = 0; i < m; i++)
    {
        t[i].parent = -1;
        t[i].left = -1;
        t[i].right = -1;
    }
    int INF = 0x3f3f3f3f;
    int min1, min2, pos1, pos2;
    for (int i = n; i < m; i++)
    {
        min2 = min1 = INF;
        for (int j = 0; j < i; j++)
        {
            if (t[j].parent == -1)
            {
                if (t[j].w < min1)
                {
                    pos2 = pos1;
                    min2 = min1;
                    pos1 = j;
                    min1 = t[j].w;
                }
                else
                {
                    if (t[j].w < min2)
                    {
                        pos2 = j;
                        min2 = t[j].w;
                    }
                }
            }
        }
        t[i].left = pos1;
        t[i].right = pos2;
        t[i].w = t[pos1].w + t[pos2].w;
        t[pos1].parent = i;
        t[pos2].parent = i;
    }
}

// 析构函数
HuffmanTree::~HuffmanTree() {}
// 按编码输出
void HuffmanTree::printHuffmanCodes()
{
    int maxn = 0, pos = 0;
    for (int i = 1; i <= n; i++)
    {
        maxn = 0;
        for (int j = 0; j < n; j++)
        {
            if (t[j].w > maxn)
            {
                maxn = t[j].w;
                pos = j;
            }
        }
        t[pos].w = -1;
        int pos1;
        string s;
        while (t[pos].parent != -1)
        {
            pos1 = t[pos].parent;
            if (t[pos1].left == pos)
                s = '0' + s;
            else
                s = '1' + s;
            pos = pos1;
        }
        cout << maxn << ":" << s << endl;
    }
    return;
}
